A traffic class is a logical grouping of traffic flows that share the same characteristics—a specific application, protocol, address or set of addresses. A flow is a single instance of a connection, session or packet-exchange activity by an identified traffic class. For example, all packets in a TCP connection belong to the same flow, as do all packets in a UDP session.
Traffic classes have the property, or class attribute, of being directional, i.e. all traffic flowing inbound will belong to different traffic classes and be monitored and managed separately from traffic flowing outbound. The directional property enables asymmetric classification and control of traffic, i.e., inbound and outbound flows belong to different classes that may be managed independent of one another.
Traffic classes may be defined at any level of the TCP/IP protocol. For example, at the IP level, traffic may be defined as only those flows between a set of inside and outside IP addresses or domain names. An example of such a low level traffic class definition would be all traffic between my network and other corporate offices throughout the Internet. At the application level, traffic classes may be defined for specific URLs within a web server. Traffic classes may be defined having “Web aware” class attributes. For example, a traffic class could be created such as all URLs matching “*.html” for all servers, or all URLs matching “*.gif” for server X, or for access to server Y with URL “/sales/*” from client Z, wherein ‘*’ is a wildcard character, i.e., a character which matches all other character combinations. Traffic class attributes left unspecified will simply match any value for that attribute. For example, a traffic class that accesses data objects within a certain directory path of a web server is specified by a URL of the directory path to be managed, e.g. “/sales/*”.
The classification of traffic is well-known in the art. For example, U.S. Pat. No. 6,285,658 describes a method for classifying traffic according to a definable set of classification attributes selectable by the manager, including selecting a subset of traffic of interest to be classified. As described therein, the ability to classify and search traffic is based upon multiple orthogonal classification attributes.
Traffic class membership may be hierarchical. Thus, a flow may be classified by a series of steps through a traffic class tree, with the last step (i.e., at the leaves on the classification tree) specifying the specific traffic class that the flow belongs to. For example, the first step in classification may be to classify a flow as web traffic, the next may further classify this flow as belonging to server X, and the final classification may be a match for URI “*.avi”.
A classification tree is a data structure representing the hierarchical aspect of traffic class relationships. Each node of the classification tree represents a class, and has a traffic specification, i.e., a set of attributes or characteristics describing the traffic, and a mask associated with it. Leaf nodes of the classification tree may contain policies (information about how to control the class of traffic). The classification process checks at each level if the flow being classified matches the attributes of a given traffic class. If it does, processing continues down to the links associated with that node in the tree. If it does not, the matching process continues on with the next (sibling) class. The last sibling in the tree must always be a default (match-all) class to catch any flows that did not match any of the classes in the rest of the tree.
More specifically, the classification tree is a N-ary tree with its nodes ordered by specificity. For example, in classifying a particular flow in a classification tree ordered first by organizational departments, the attributes of the flow are compared with the traffic specification in each successive department node and if no match is found, then processing proceeds to the next subsequent department node. If no match is found, then the final compare is a default “match all” category. If, however, a match is found, then classification moves to the children of this department node. The child nodes may be ordered by an orthogonal paradigm such as, for example, “service type.” Matching proceeds according to the order of specificity in the child nodes. Processing proceeds in this manner, traversing downward and from left to right in the classification tree, searching multiple orthogonal paradigms. The nodes are often arranged in decreasing order of specificity to permit searching to find the most specific class for the traffic before more general.
A number of problems exist with using classification trees. First, tree-based classification is an inherently slow process. As discussed above, it requires walking the classification tree one node at a time searching for matches until a class is found that matches the incoming flow or packet. In a large tree, this becomes very time consuming. For example, in the case of an Internet Service Provider (ISP) wanting to classify an incoming flow/packet by address, when they have thousands of customers, a large amount of time would be expended walking down the tree to locate a match.
Second, another problem that may exist is that a class tree may have a number of types of classes. For example, a classification tree may include IP addresses, services, and ports. However, there is no a-priori specification as to which of the multiple types of classes to attempt to match first.